COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "memo.pub[let,jmc]" source
C00008 00003	REFERENCES:
C00009 ENDMK
C⊗;
.require "memo.pub[let,jmc]" source;
.cb A Classification of Problems in AI


	The object of this classification of problems is
partly to show that most of the work in AI has concentrated
on a small class of problems but also with the idea that
each new difficulty can best be considered apart from the others.

	The first classification is based on the dichotomy -
⊗physical vs. ⊗mental.  A problem is considered physical
if the information presented is entirely physical, i.e.
about physical states and the effects of physical actions.
The problem-solver may have to think, but it has only
to think about the physical effects of its actions and
those of others.
The correct notion of physical action is quite general, e.g.
may include buying and selling, but it does not include
actions whose purpose is communication - or at least it doesn't
consider the communication effects of these actions.

	In a mental problem, one has also to
think about ⊗knowledge (where it is, who has it, and how to
get it) and ⊗wants, e.g. what does he want.
We consider a problem mental if the actions include communication.
Naturally a mental problem may have a physical part, so
to declare a problem physical is to reduce it to a subdomain.
Perhaps the case when the solver must think only about its
own lack of knowledge, and not about the location of knowledge
in telephone books and other people is special.

	The second classification is ⊗static vs. ⊗dynamic.  A static
problem is one where certain facts about a situation are known,
and the problem is to answer certain questions about that situation.
In dynamic problems the situation changes.

	A popular subclass of dynamic problems is called ⊗quasi-static. 
In a quasi-static problem, the solver must make a move in a situation,
and this results in a new situation.  His problem is to make a sequence
of moves leading to a situation that satisfies a goal condition.
Time and actions are discrete, and the solver doesn't have to
consider several processes going on at once, perhaps at unknown
relative rates.  

	Most of the problems considered in AI research have been
quasi-static, and people sometimes formulate the AI problem
as though all problems were quasi-static.  I'll strengthen that
remark; I know of no AI work on truly dynamic problems.

	Within the quasi-static problems, we can make some distinctions.
First, the required solution may be a sequence of moves, and this
is presumably simpler than the case when the solution is a program like
%2go South on El Camino until you come to a Mobil gas station%1.
Second, the state of the system may  or may not be completely known;
this is discussed by Robert C. Moore (1975) in his M.I.T. M.S. thesis.
As Moore points out, most work has concentrated on
the easy case of complete knowledge.

	It seems worthwhile to give some examples of problems that
embody the less studied features, but which are still not too
difficult.

.bb Some Problems.
.item←0;

	#. Consider traders who buy and sell commodities.  Suppose
they communicate by telephone making offers to buy and sell.
They have models of each others wants and knowledge.  They operate
in continuous time although each transaction is discrete.  Different
pairs deal in parallel.  Because of the parallel action, the result
formalism of (McCarthy and Hayes 1970) will not be directly suitable
for expressing the facts.  However, it would seem that the problem
could be modified so as to make this formalism usable.
REFERENCES:

Moore, Robert C. (1975), %2Reasoning From Incomplete Knowledge in a
Procedural Deduction System%1. Artificial Intelligence Laboratory,
M.I.T.

This version of PROBLE[S76,JMC]@SU-AI was PUBbed on {date}.